package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName Medium_22_GenerateParenthesis
 * @Description Medium_22_GenerateParenthesis
 * @Author wanghaiwei
 * @Date 2023/2/6 17:54
 */
public class Medium_22_GenerateParenthesis {
    public List<String> generateParenthesisByBacktrack(int n) {
        List<String> results = new ArrayList<>();
        if (n == 0) {
            return results;
        }
        backtrack("", n, n, results);
        return results;
    }

    /**
     * @param currStr            当前搜索过程的结果
     * @param leftBracketAmount  剩余的左括号数量
     * @param rightBracketAmount 剩余的右括号数量
     * @param results            总结果集合
     */
    public void backtrack(String currStr, int leftBracketAmount, int rightBracketAmount, List<String> results) {
        //左右括号都用完了，说明形成了一个解，添加到总集合中
        if (leftBracketAmount == 0 && rightBracketAmount == 0) {
            results.add(currStr);
            return;
        }
        //剪枝情况：这种情况是先用掉了一个右括号，那么多余的左括号就没法配对了
        if (leftBracketAmount > rightBracketAmount) {
            return;
        }
        //没有用for语句，是因为只有左括号和右括号两种情况，直接展开成两次调用即可
        if (leftBracketAmount > 0) {
            backtrack(currStr + "(", leftBracketAmount - 1, rightBracketAmount, results);
        }
        if (rightBracketAmount > 0) {
            backtrack(currStr + ")", leftBracketAmount, rightBracketAmount - 1, results);
        }
    }

    /**
     * 动态规划解法
     *
     * @param n
     * @return
     */
    private List<String> generateParenthesisByDynamicPrograming(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        List<List<String>> memoRes = new ArrayList<>();
        memoRes.add(new ArrayList<>(Arrays.asList(""))); //0
        memoRes.add(new ArrayList<>(Arrays.asList("()"))); //1
        memoRes.add(new ArrayList<>(Arrays.asList("(())", "()()")));//2
        memoRes.add(new ArrayList<>(Arrays.asList("((()))", "(()())", "(())()", "()(())", "()()()")));//3
        for (int i = 4; i <= n; i++) {
            List<String> resForI = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                List<String> subResForJ = memoRes.get(j);
                List<String> subResForOtherPart = memoRes.get(i - 1 - j);
                for (String strForJ : subResForJ) {
                    for (String strForOtherPart : subResForOtherPart) {
                        resForI.add("(" + strForJ + ")" + strForOtherPart);
                    }
                }
            }
            memoRes.add(resForI);
        }
        return memoRes.get(n);
    }

    public static void main(String[] args) {
        Medium_22_GenerateParenthesis solution = new Medium_22_GenerateParenthesis();
        List<String> result = solution.generateParenthesisByBacktrack(3);
        List<String> expect = new ArrayList<>(Arrays.asList("((()))", "(()())", "(())()", "()(())", "()()()"));
        expect.removeAll(result);
        Assert.isTrue(expect.size() == 0, "generateParenthesisByBacktrack：n = 3计算错误，预期[\"((()))\",\"(()())\",\"(())()\",\"()(())\",\"()()()\"]，实际：" + StringUtils.join(result));


        result = solution.generateParenthesisByDynamicPrograming(4);
        expect = new ArrayList<>(Arrays.asList("(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"));
        expect.removeAll(result);
        Assert.isTrue(expect.size() == 0, "generateParenthesisByBacktrack：n = 4计算错误，预期[\"(((())))\",\"((()()))\",\"((())())\",\"((()))()\",\"(()(()))\",\"(()()())\",\"(()())()\",\"(())(())\",\"(())()()\",\"()((()))\",\"()(()())\",\"()(())()\",\"()()(())\",\"()()()()\"]，实际：" + StringUtils.join(result));

        result = solution.generateParenthesisByDynamicPrograming(3);
        expect = new ArrayList<>(Arrays.asList("((()))", "(()())", "(())()", "()(())", "()()()"));
        expect.removeAll(result);
        Assert.isTrue(expect.size() == 0, "generateParenthesisByDynamicPrograming：n = 3计算错误，预期[\"((()))\",\"(()())\",\"(())()\",\"()(())\",\"()()()\"]，实际：" + StringUtils.join(result));


        result = solution.generateParenthesisByDynamicPrograming(4);
        expect = new ArrayList<>(Arrays.asList("(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"));
        expect.removeAll(result);
        Assert.isTrue(expect.size() == 0, "generateParenthesisByDynamicPrograming：n = 4计算错误，预期[\"(((())))\",\"((()()))\",\"((())())\",\"((()))()\",\"(()(()))\",\"(()()())\",\"(()())()\",\"(())(())\",\"(())()()\",\"()((()))\",\"()(()())\",\"()(())()\",\"()()(())\",\"()()()()\"]，实际：" + StringUtils.join(result));
    }
}
